package airthmetic.exercise.sort.cmp;


// 归并排序
public class _912_排序数组_Merge2 {
    int[] temp;
    public int[] sortArray(int[] nums) {
        if(nums == null || nums.length < 2){
            return nums;
        }
        temp =new int[nums.length];
        mergeSort(nums, 0, nums.length-1);
        return nums;
    }
    public void mergeSort(int[] nums, int left, int right){
        // terminal
        if(left == right){
            return;
        }
        // process current logic
        int mid = ((right - left) >> 1) + left;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid+1, right);

        int i=left;
        int j=mid+1;
        int k=0;

        while(i<=mid && j<=right){
            if(nums[i] <= nums[j]){
                temp[k++] = nums[i++];
            }else{
                temp[k++] = nums[j++];
            }
        }
        while(i<=mid){
            temp[k++] = nums[i++];
        }

        while(j<=right){
            temp[k++] = nums[j++];
        }

        for(int m=right; m>=left; m--){
            nums[m] = temp[--k];
        }
    }
}
